package com.platform.modules.alg.alglib.poj1330;

public class Poj1330 {
    private final int maxn = 10010;
    private int fa[] = new int[maxn];
    private boolean flag[] = new boolean[maxn];
    public String output = "";

    void Init(int n) {
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            flag[i] = false;
        }
    }

    int LCA(int u, int v) {
        if (u == v)
            return u;
        flag[u] = true;
        while (fa[u] != u) { // u 向上走到根
            u = fa[u];
            flag[u] = true;
        }
        if (flag[v])
            return v;
        while (fa[v] != v) { // v 向上
            v = fa[v];
            if (flag[v])
                return v;
        }
        return 0;
    }

    public String cal(String input) {
        int n, u, v;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        Init(n);
        for (int i = 1; i < n; i++) {
            String[] words = line[i].split(" ");
            u = Integer.parseInt(words[0]);
            v = Integer.parseInt(words[1]);
            fa[v] = u;
        }
        String query[] = line[n].split(" ");
        u = Integer.parseInt(query[0]);
        v = Integer.parseInt(query[1]);
        output = LCA(u, v) + "\n";
        return output;
    }
}
